package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.*;

/**
 * 贪心算法实例，集合覆盖问题
 *
 * @author zjj_admin
 * @date 2022/12/31 14:14
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {
        //创建广播电台
        Map<String, HashSet<String>> boardCast = new HashMap<>();
        HashSet<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");

        HashSet<String> set2 = new HashSet<>();
        set2.add("北京");
        set2.add("广州");
        set2.add("深圳");

        HashSet<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");

        HashSet<String> set4 = new HashSet<>();
        set4.add("天津");
        set4.add("上海");

        HashSet<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");

        //加入到 map
        boardCast.put("K1", set1);
        boardCast.put("K2", set2);
        boardCast.put("K3", set3);
        boardCast.put("K4", set4);
        boardCast.put("K5", set5);
        List<String> res = getBoardCast(boardCast);
        System.out.println("res = " + res);
    }


    /**
     * 获取最少的电台覆盖所有的城市
     *
     * @param boardCast 电台集合
     * @return
     */
    public static List<String> getBoardCast(Map<String, HashSet<String>> boardCast) {
        List<String> res = new ArrayList<>();
        //保存所有的地区
        HashSet<String> allAreas = new HashSet<>();

        for (Map.Entry<String, HashSet<String>> entry : boardCast.entrySet()) {
            HashSet<String> cities = entry.getValue();
            allAreas.addAll(cities);
        }
        //定义一个辅助的map，用于存放当前每一个电台可以覆盖最多的没有覆盖的城市
        Map<String, Integer> help = new HashMap<>();

        while (!allAreas.isEmpty()) {
            for (Map.Entry<String, HashSet<String>> entry : boardCast.entrySet()) {
                //获取电台的名称
                String key = entry.getKey();
                HashSet<String> cities = entry.getValue();
                int count = 0;
                for (String city : cities) {
                    if (allAreas.contains(city)) {
                        count++;
                    }
                }
                help.put(key, count);
            }
            //遍历 help 集合，获取最多的尾覆盖城市的电台
            String maxCityBoardCast = "";
            int maxCity = 0;
            for (Map.Entry<String, Integer> entry : help.entrySet()) {
                if (entry.getValue() > maxCity) {
                    //这样就可以选出一个电台了
                    maxCityBoardCast = entry.getKey();
                    maxCity = entry.getValue();
                }
            }
            //将 maxCityBoardCast 添加到返回数据中
            res.add(maxCityBoardCast);
            //将 maxCityBoardCast 中的城市从所有地区中移除
            HashSet<String> cities = boardCast.get(maxCityBoardCast);
            allAreas.removeAll(cities);
            //将当前选中的广播站从 boardCast 里面移除即可，同时也必须从 help 中移除。这个可以不用移除，对效率不会产生太大的影响
            boardCast.remove(maxCityBoardCast);
            help.remove(maxCityBoardCast);
        }
        return res;
    }


}
